//
// Created by jizhe hu on 2024/1/24.
//

#ifndef LEETCODE_STR_H
#define LEETCODE_STR_H
#include <vector>
#include <stack>
#include <string>

using namespace std;

//! 344.反转字符串
void reverseString(vector<char>& s) {
    int n = s.size();
    for(int i=0; i< (n / 2); i++) {
        char tmp = s[i];
        s[i] = s[n - 1 - i];
        s[n - 1 - i] = tmp;
    }
}

//! 541. 反转字符串 II
string reverseStr(string s, int k) {
    auto func = [](string::iterator first, string::iterator last) {
        while(first < last) {
            auto c = *first;
            *first = *last;
            *last = c;
            first++;
            last--;
        }
    };
    int n = s.size();
    int cur_index = 0;
    while(1) {
        if((n - cur_index) < k) {
            func(s.begin() + cur_index, s.begin() + (n - 1));
            return s;
        } else if ((n - cur_index) < k * 2) {
            func(s.begin() + cur_index, s.begin() + cur_index + k - 1);
            return s;
        } else {
            func(s.begin() + cur_index, s.begin() + cur_index + k - 1);
            cur_index += k * 2;
        }
    }
    return s;
}

//! 替换数字
void replaceNumber(string & s) {
    int sz = 0;
    int old_sz = s.size();
    for(const auto& elem : s) {
        if(elem >= '0' && elem <= '9') {
            sz += 6;
        } else {
            sz += 1;
        }
    }
    s.resize(sz);
    for(int i=old_sz-1; i>=0; i--) {
        if(s[i] >= '0' && s[i] <= '9') {
            s[sz - 6] = 'n';
            s[sz - 5] = 'u';
            s[sz - 4] = 'm';
            s[sz - 3] = 'b';
            s[sz - 2] = 'e';
            s[sz - 1] = 'r';
            sz -= 6;
        } else {
            s[sz - 1] = s[i];
            sz--;
        }
    }
}

//! 151.反转字符串中的单词
string reverseWords(string s) {
    int n = s.size();
    int l_prev = 0, l_last = 0;

    int i = 0;
    for(i=0;i<n;i++) {
        if(s[i] != ' ') break;
    }

    s.erase(0, i);

    while (s.back() == ' ') s.pop_back();
    n = s.size();

    for (int i=0 ;i<n; i++) {
        if(s[i] == ' ') {
            int j = i;
            while(s[j+1] == ' ') {
                j++;
            }
            s.erase(i, j - i);
            n -= (j-i);
        }
    }

    std::reverse(s.begin(), s.end());

    while (true) {
        while(l_last < n && s[l_last] != ' ') {
            l_last++;
        }
        std::reverse(s.begin() + l_prev, s.begin() + l_last);
        l_prev = l_last + 1;
        l_last = l_prev;
        if(l_last > n) break;
    }
    return s;
}

void getNext(vector<int>& next, const string& s) {
    int j = 0;
    next[0] = 0;
    for(int i = 1; i < s.size(); i++) {
        while (j > 0 && s[i] != s[j]) {
            j = next[j - 1];
        }
        if (s[i] == s[j]) {
            j++;
        }
        next[i] = j;
    }
}

//! 28. 找出字符串中第一个匹配项的下标
int strStr(string haystack, string needle) {
    vector<int> next(needle.size());
    getNext(next, needle);
    int j = 0;
    for(int i=0; i<haystack.size(); i++) {
        while(j > 0 && haystack[i] != needle[j]) {
            j = next[j - 1];
        }
        if(haystack[i] == needle[j]) {
            j++;
        }
        if(j == needle.size()) return i - needle.size() + 1;
    }
    return -1;
}

//! 459.重复的子字符串
bool repeatedSubstringPattern(string s) {
    vector<int> next(s.size());
    getNext(next, s);
    int val = next.back();
    if(val > 0 && s.size() % (s.size() - val) == 0) return true;
    return false;
}

#endif //LEETCODE_STR_H
